返回
转到题目
【待完善】
题目思路:
题意说明,我们需要在在一堆混乱的牌中找到两个不同的才能获胜。 此时我们还知道有n种牌,以及他们的数目.我们可以通过预知某些牌的种类来帮助我们获胜 求这个最小能保证我预测后一定获胜的预测数
- 我们要求最小,但我们要知道一般的,能够让我获胜的预测数是怎么样的.
- 特殊地，如果我们全部知道了,我们自然知道怎么选了.
- 我们贪心地缩小一下,如果我们预测中存在2种及以上的牌种数,也是可以的
- 再缩小一下,如果我们预测中一种牌，但这种牌全被预测了,剩下的任选都满足,也是可以的
- 再小呢?再小就不能通过这个性质一眼判别了
我们当前知道了,通过以上性质判别的,最少就是一种元素的全部，这个是对于单个元素. 如果考虑到一堆牌,我们要保证n次后出结果,而每种元素预测了t>=x时一定出结果, 而每种牌都可能有极限情况,为了保证任何情况都满足,我们取 res = max(li)
到这里你以为结束了?不！ 以上只推导了一种性质的证明,但实际上还有else情况,结果取俩中较小。 我们从上面性质的反面思考: 如果我们为了让选的牌不一样，我预测后能确定剩下的牌中和有解。求这个的最小预测数。 我们能让剩下的牌中任意选，一定不一样，怎么样预测? 通过分析可以观察到,如果我们剩下的全是每种牌就一种没预测的情况，就一定任意选可行
- 以上是普遍情况，我们怎么最小化?
- 如果预测的种类大于等于2，我们正面可以得到解，但我要考虑反面的话,还要最小的话,一定是没有预测一种牌的预测数少的，因此大于等于2的情况被舍弃了
- 如果是一种牌，我要考虑反面那我要预测 sum - n 次让剩下的都是1